package org.zxp.datastructure.link;

import org.junit.Test;

/**
 * @program: effectiveJava
 * @description:自己实现的单向链表
 * @author: X-Pacific zhang
 * @create: 2019-07-11 11:38
 **/
public class LinkedListSelf {
    static LinkedListSelf linkedList = null;
    static{
        linkedList = new LinkedListSelf();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");
        linkedList.add("E");
    }

    public static void main(String[] args) throws Exception {
        LinkedListSelf linkedListSelf = new LinkedListSelf();
        linkedListSelf.add("A");
        linkedListSelf.add("B");
        linkedListSelf.add("C");
        linkedListSelf.add("D");
        linkedListSelf.add("E");

        linkedListSelf.add("w", 2);

        linkedListSelf.delete();
        linkedListSelf.delete(2);

        linkedListSelf.printAll();
    }

    @Test
    public void testdel() throws Exception {
        LinkedListSelf linkedListSelf = new LinkedListSelf();
        linkedListSelf.add("A");
        System.out.println(linkedListSelf.delete().data);
        System.out.println(linkedListSelf.delete(1));
    }

    @Test
    public void testreverse() {
        linkedList.reverse();
        linkedList.print(linkedList.last);
    }

    @Test
    public void testCircle(){
        System.out.println(linkedList.existsCircle());
        System.out.println(linkedList.makeitCircle().existsCircle());
    }


    public void reverse() {
        Node preNode = first;
        Node curNode = first.next;
        Node nextNode = first.next.next;
        first.next = null;
        while (nextNode != null) {
            curNode.next = preNode;

            preNode = curNode;
            curNode = nextNode;
            nextNode = nextNode.next;
        }
        curNode.next = preNode;
    }

    public boolean existsCircle(){
        Node testfirst = this.first;
        Node node = first.next;
        while (node != null) {
            if(testfirst == node){
                return true;
            }
            node = node.next;
        }
        return false;

//        if(last.next == first){
//            return true;
//        }else{
//            return false;
//        }
    }

    public LinkedListSelf makeitCircle(){
        last.next = first;
        return this;
    }


    private int size = 0;
    Node last = null;
    Node first = new Node("FIRST", last);

    /**
     * 链表尾部添加node
     *
     * @param data
     */
    public void add(String data) {
        Node newNode = new Node(data, null);
        if (first.next == null) {
            first.next = newNode;
            last = newNode;
        } else {
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    /**
     * 打印数组全部内容
     */
    public void printAll() {
        Node node = first.next;
        while (node != null) {
            System.out.print(node.data);
            System.out.println();
            node = node.next;
        }
    }

    /**
     * 从node开始打印
     */
    public void print(Node node) {
        while (node != null && !node.data.equals("FIRST")) {
            System.out.print(node.data);
            System.out.println();
            node = node.next;
        }
    }

    /**
     * 根据下标找到node
     *
     * @param index
     * @return
     * @throws Exception
     */
    private Node node(int index) throws Exception {
        if (index > size - 1) {
            throw new Exception("没有找到下标节点");
        }
        Node node = first.next;
        int cur = 0;
        while (node != null) {
            if (index == cur++) {
                return node;
            }
            node = node.next;
        }
        throw new Exception("没有找到下标节点");
    }

    /**
     * 指定位置添加node
     *
     * @param data
     * @param index
     */
    public void add(String data, int index) throws Exception {
        check(index);
        Node nextNode = null;
        Node preNode = null;
        if (index == 0) {
            preNode = first;
            nextNode = first.next;
        } else {
            preNode = node(index - 1);
            nextNode = preNode.next;
        }
        Node node = new Node(data, nextNode);
        preNode.next = node;
        size++;
    }

    /**
     * 删除尾部的node
     */
    public Node delete() throws Exception {
        Node delNode = null;
        if (first.next == null) {
            return null;
        } else if (size == 1) {
            delNode = first.next;
            first.next = null;
            return delNode;
        } else {
            delNode = last;
            Node node = node(size - 2);
            last = node;
            last.next = null;
        }
        return delNode;
    }

    /**
     * 删除指定位置的node
     *
     * @param index
     */
    public Node delete(int index) throws Exception {
        check(index);
        Node delNode = null;
        Node preNode = null;
        Node nextNode = null;

        if (index == 0) {
            delNode = first.next;
            preNode = first;
            nextNode = first.next.next;
        } else if (index == size - 1) {
            preNode = node(index - 1);
            delNode = last;
            nextNode = last.next;
        } else {
            preNode = node(index - 1);
            delNode = preNode.next;
            nextNode = delNode.next;
        }
        preNode.next = nextNode;
        return delNode;
    }

    /**
     * 检查是否越界
     *
     * @param index
     * @throws Exception
     */
    private void check(int index) throws Exception {
        if (index > size - 1) {
            throw new Exception("index out of bound!");
        }
    }


    static class Node {
        String data;
        Node next;

        public Node(String data) {
            this.data = data;
            next = null;
        }

        public Node(String data, Node next) {
            this.data = data;
            this.next = next;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
}
